\section{Our technique}
\label{sec-our-technique}

\subsection{First-class global environments}
\label{sec-first-class-global-environments}

Most \commonlisp{} systems have a single global environment.  Part of
that environment is typically located in slots of symbols.  In
particular, a symbol often contains a \emph{value cell} and a
\emph{function cell}.  In contrast \sicl{} uses first-class global
environments \cite{Strandh:2015:ELS:Environments} that contain this
information, as well as information about classes, types, etc.
With this technique, the name of a function can be associated with
different functions in different global environments.

We invented first-class global environments for two distinct reasons:

\begin{itemize}
\item We want \sicl{} to be a \emph{safe} system.  Part of this safety
  involves protecting the system code itself from malicious external
  software.  In particular, the default global environment contains
  only functionality that the \commonlisp{} standard dictates.  Parts
  of the system (such as the compiler) are contained in a separate
  global environment that requires some additional manipulation to
  access.
\item \sicl{} is bootstrapped
  \cite{Durand-Strandh:2019:ELS:Bootstrapping} on an existing
  \commonlisp{} implementation.  We use first-class global
  environments to isolate the \sicl{} code from the host system during
  bootstrapping.
\end{itemize}

\subsection{Bootstrapping}

The bootstrapping procedure of \sicl{} first creates an acyclic graph
of metaobjects.  At the end of this process, we have a constellation
of objects in the last two first-class global environments that can be
illustrated as shown in \refFig{fig-constellation}.

\begin{figure}
\begin{center}
\inputfig{fig-constellation.pdf_t}
\end{center}
\caption{\label{fig-constellation}
Constellation of metaobjects in the acyclic graph.}
\end{figure}

In \refFig{fig-constellation}, we see two environments.  The last one
created is labeled N and the preceding one is labeled N-1.  Slots such
as the list of methods, the call history, etc. of a generic function
in environment N can be accessed only by accessor generic functions in
environment N-1.  Other generic functions in environment N-1 must call
the accessors, also in environment N-1, in order to accomplish
higher-level tasks.  In particular, in this paper we are interested in
two such higher-level tasks: computing effective-method functions and
computing the discriminating function.

Although both these tasks involve calling other functions, generic or
not, we are interested only in the result of calling the function
\texttt{compile}.  The generic function
\texttt{compute-effective-method} returns a lambda expression
containing individual method functions as constants.  The function
\texttt{compile} is then called in order to turn that lambda
expression into a function.  Similarly, as described in our paper on
generic dispatch \cite{Strandh:2014:FGD:2635648.2635654}, the generic
function \texttt{compute-discriminating-function} creates  a lambda
expression consisting of a tree of tests for argument classes, the
leaves of that tree being effective-method functions.  Again, the
function \texttt{compile} is called in order to turn this lambda
expression into a function.

\subsection{Properties of functions in the acyclic graph}

When source code is turned into a function by \texttt{compile}, the
resulting function object contains two parts: the
\emph{compiled code} and the \emph{static environment}.  In \sicl{},
the static environment of a function $f$ contains non-trivial
constants referred to by $f$, but most importantly, it contains the
function cells of functions that are called by $f$.  These function
cells are taken from the first-class global environment in which $f$
was compiled.

For the purpose of this work, we are interested in two important
properties of both ordinary functions and generic functions in the
acyclic graph illustrated by \refFig{fig-constellation}.

\begin{definition}
A function is \emph{present} in some environment $E$ if and only if it
is referred to by some function cell in $E$.
\end{definition}

\begin{definition}
A function is \emph{tied} to some environment $E$ if and only if every
function cell in its static environment is a function cell in $E$.
\end{definition}

In general, a function can be present in some environment $E$ without
being tied to $E$.  In fact, this property is essential for the safety
issue discussed in \refSec{sec-first-class-global-environments}.  An
important function such as \texttt{compile} will be accessible in the
default environment, but the functions that it calls for tasks such as
generating native code, will not be present in that default
environment.

However, in order to create the initial \sicl{} system, we need an
initial global environment, and all functions that are present in this
environment must also be tied to this initial environment.  The way
that we accomplish this task is the subject of the remainder of this
paper.

\subsection{Structure of a generic function in environment N}

Let us now examine the structure of the discriminating function of a
generic function in environment N in \refFig{fig-constellation}, and
in particular, the function \texttt{compute-discriminating-function}.
The method functions of a generic function in environment N are tied
to environment N, simply because they were compiled by the function
\texttt{compile} tied to environment N.  However, the effective-method
functions and the discriminating function were produced by the
function \texttt{compile} tied to environment N-1.  This situation is
illustrated by \refFig{fig-structure-of-generic-function}.

\begin{figure}
\begin{center}
\inputfig{fig-structure-of-generic-function.pdf_t}
\end{center}
\caption{\label{fig-structure-of-generic-function}
Structure of a generic function in environment N.}
\end{figure}

As \refFig{fig-structure-of-generic-function} illustrates, we have a
mixture of functions tied to environment N-1 and functions tied to
environment N.  In particular, as part of the argument test code, when
the function is called with an argument that has not yet been seen,
several other functions tied to environment N-1 are called in order to
compute a new effective-method function, to update the call history,
and ultimately to compute a new discriminating function.  This process
is described in our paper on generic dispatch
\cite{Strandh:2014:FGD:2635648.2635654}.

A discriminating function with this kind of mixture of sub-functions
tied to different environments is said to be \emph{impure}.  For a
discriminating function to be considered pure, all the functions that
it consists of must be tied to environment N.

\subsection{Turning the structure cyclic}

To see how we can ensure that every part of the discriminating
function is tied to environment N, we must first introduce another
level of environments.  We omitted the accessor generic functions in
environment N of \refFig{fig-constellation}, but now we need to
understand their capabilities.  In \refFig{fig-constellation-2}, we
have added the environment N+1 in order to illustrate our technique.

\begin{figure}
\begin{center}
\inputfig{fig-constellation-2.pdf_t}
\end{center}
\caption{\label{fig-constellation-2}
Accessors in environment N.}
\end{figure}

As \refFig{fig-constellation-2} illustrates, an accessor generic
function in environment N is created in order to access slots of
generic functions in environment N+1.  However, as
\refFig{fig-constellation-2} also illustrates, an accessor generic
function in environment N is also capable of accessing slots of
generic functions in environment N.  The reason for that capability is
that generic functions in environment N and generic functions in
environment N+1 have the identical structure, aside from the reference
to class objects of which they are instances.  The details of how the
bootstrapping procedure results in this similar structure is explained
in detail in our bootstrapping paper
\cite{Durand-Strandh:2019:ELS:Bootstrapping}.

This similar structure of generic functions in environment N and
generic functions in environment N+1 suggests that we should be able
to call \texttt{compute-discriminating-function} in environment N,
passing it itself as an argument.  For that self application to work,
there must already be an installed discriminating function that is
capable of handling standard generic functions as arguments. 

There are several ways in which we can create a discriminating
function for \texttt{compute-discriminating-function} in environment N
and then install it.  One simple way is to just call it, passing it
any generic function in either environment N or environment N+1.  The
machinery in environment N-1 will then be invoked and an impure
discriminating function will be installed.  We can then call
\texttt{compute-discriminating-function} on itself to recompute the
discriminating function.  Unfortunately, this idea does not work.  The
reason is that \texttt{compute-discriminating-function} does not alter
the call history, and the call history contains effective-method
functions tied to environment N-1.  The result of this operation would
therefore be a situation illustrated by
\refFig{fig-structure-of-generic-function-2}.

\begin{figure}
\begin{center}
\inputfig{fig-structure-of-generic-function-2.pdf_t}
\end{center}
\caption{\label{fig-structure-of-generic-function-2}
Structure of a generic function after self application.}
\end{figure}

%%  LocalWords:  accessors metaobjects accessor immediates metaobject

Though the operation does not have the desired result, we should point
out that we could have turned the two calls into a single one, namely,
passing \texttt{compute-discriminating-function} in environment N as
an argument to itself.  The existing discriminating function is then
computed from an empty call history, so the machinery for computing an
effective-method function in environment N-1 is invoked and a new
discriminating function with the structure illustrated in
\refFig{fig-structure-of-generic-function} would be installed.  This
new discriminating function would then be re-invoked on itself, again
resulting in a structure illustrated by
\refFig{fig-structure-of-generic-function-2}.

In order for the result to be a pure discriminating function, we would
have to clear and recompute the call history.  But if we clear the
call history and recompute the discriminating function,
\texttt{compute-discriminating-function} will no longer be
operational.  We must therefore find a different way.

In our paper on satiation \cite{Strandh:2014:RMI:2635648.2635656}, we
describe a technique that allows us to fill the call history of a
generic function with every possible argument combination for which at
least one applicable primary method exists.  This technique works as
follows:

\begin{enumerate}
\item First the existing call history is cleared.  This step does not
  alter the installed discriminating function.
\item Then, each primary method is examined in order to determine
  what combination of classes of arguments would make it applicable.
  A method is applicable if the argument corresponding to every
  specialized parameter is an instance of some subclass of the
  specializer class.
\item For each such combination of argument classes, where each class
  being represented by its unique number (see
  \cite{Durand-Strandh:2019:ELS:Bootstrapping}), an effective method
  is computed, and \texttt{compile} is applied to it in order to
  create an effective-method function.  The class numbers and the
  effective-method function form an entry of the call history.
\item Finally, \texttt{compute-discriminating-function} is called to
  compute a discriminating function from the call history, and the
  resulting discriminating function is installed using
  \texttt{set-funcallable-instance-function}.
\end{enumerate}

The name of the function that accomplishes this task is
\texttt{satiate-generic-function} and it is itself a generic
function.  If we load that function into environment N and then call
it on itself, the following steps will take place:

\begin{enumerate}
\item Initially, the call history of \texttt{satiate-generic-function}
  is empty and its discriminating function is not operational on the
  class of argument (i.e., a standard generic function) that it was
  given.  Therefore, the machinery of environment N-1 will be invoked
  to compute an impure discriminating function for it.
\item Once operational, \texttt{satiate-generic-function} will be
  invoked again, again with itself as an argument.
\item The call history will be cleared, and a new one will be
  computed, containing, among other things, an entry for the class
  \texttt{standard-generic-function} and a corresponding
  effective-method function.  This step is accomplished by the
  existing installed impure discriminating function.  The
  effective-method function is created using \texttt{compile} in
  environment N, since that is the environment to which method
  functions on \texttt{satiate-generic-function} are tied.
\item A new discriminating function will be computed by a call to
  \texttt{compute-discriminating-function}, also in environment N.
\item Finally, this new pure discriminating function is installed.
\end{enumerate}

No matter which generic function $f$ in environment N is passed as an
argument to \texttt{satiate-generic-function}, a new pure
discriminating function will be computed and installed in $f$.  And,
in fact, \texttt{satiate-generic-function} can be called with the
generic functions in environment N in some arbitrary order.
